#define _CRT_SECURE_NO_WARNINGS

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> nums1(nums.begin(), nums.end());
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        stack<int>s;
        vector<int>ret(nums.size(), -1);
        for (int i = 0; i < nums.size(); i++)
        {
            while (s.size() != 0 && nums[s.top()] < nums[i])
            {
                ret[s.top()] = nums[i];
                s.pop();
            }
            s.push(i);
        }
        ret.resize(nums.size() / 2);
        return ret;
    }
};

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int>s;
        vector<int>ret(nums.size(), -1);
        for (int i = 0; i < nums.size() * 2; i++)
        {
            while (s.size() != 0 && nums[s.top() % nums.size()] < nums[i % nums.size()])
            {
                ret[s.top() % nums.size()] = nums[i % nums.size()];
                s.pop();
            }
            s.push(i);
        }
        return ret;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0;
        int ret = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++)
        {
            if (st.empty())
            {
                st.push(i);
                continue;
            }
            if (height[st.top()] > height[i])
                st.push(i);
            else if (height[st.top()] == height[i])
                st.push(i);
            else
            {
                while (!st.empty() && height[st.top()] < height[i])
                {
                    int mid = st.top();
                    st.pop();
                    if (!st.empty())
                    {
                        int h = min(height[st.top()], height[i]) - height[mid];
                        int w = i - st.top() - 1;
                        ret += h * w;
                    }
                }
                st.push(i);
            }
        }
        return ret;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() <= 2) return 0;
        int ret = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++)
        {
            while (!st.empty() && height[st.top()] < height[i])
            {
                int mid = st.top();
                st.pop();
                if (!st.empty())
                {
                    int h = min(height[st.top()], height[i]) - height[mid];
                    int w = i - st.top() - 1;
                    ret += h * w;
                }
            }
            st.push(i);
        }
        return ret;
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int ret = 0;
        stack<int> st;
        for (int i = 0; i < heights.size(); i++)
        {
            while (!st.empty() && heights[i] < heights[st.top()])
            {
                int mid = st.top();
                st.pop();
                int left = st.top();
                int right = i;
                int h = heights[mid];
                int w = right - left - 1;
                ret = max(ret, h * w);
            }
            st.push(i);
        }
        return ret;
    }
};